package arithmetic2.day01;

/*
    二分法
 */
public class Demo02 {
    public static void main(String[] args) {
//        int arr[] = new int[]{1,3,6,9,10,23};
//        System.out.println(isExist(arr,23,0,arr.length-1));

        int arr[] = new int[]{1, 2, 2, 3, 3, 3, 4, 4, 5, 5};
//        int arr[] = new int[]{5,5};
//        System.out.println(leftIndex(arr,5,0,arr.length-1));
        System.out.println(rightIndex(arr, 5, 0, arr.length - 1));
    }

    //判断一个数在有序数组中是否存在
    public static boolean isExist(int arr[], int key, int start, int end) {
        if (start < end) {
            int temp = (start + end) >> 1;
            if (arr[temp] == key) {
                return true;
            } else if (arr[temp] > key) {
                return isExist(arr, key, start, temp - 1);
            } else {
                return isExist(arr, key, temp + 1, end);
            }
        }
        return arr[start] == key ? true : false;
    }

    //在一个有序数组中找出某个数第一次出现的位置
    public static int leftIndex(int arr[], int key, int start, int end) {
        if (start < end) {
            int temp = (start + end) >> 1;
            if (arr[temp] >= key) {
                return leftIndex(arr, key, start, temp);
            } else {
                return leftIndex(arr, key, temp + 1, end);
            }
        }
        return arr[start] == key ? start : -1;
    }

    //在一个有序数组中找出某个数最后一次出现的位置
    public static int rightIndex(int arr[], int key, int start, int end) {
        if (start < end) {
            int temp = (start + end + 1) >> 1;
            if (arr[temp] <= key) {
                return rightIndex(arr, key, temp, end);
            } else {
                return rightIndex(arr, key, start, temp - 1);
            }
        }
        return arr[start] == key ? start : -1;
    }
}
